package main

// 使用广度优先遍历
// 每次都是遍历一层，遍历完成就是要多少次，最简单
// 这道题的难点在于，若有多颗 腐烂的橘子，那么同一时间都进行腐烂周边， 好像是并发执行，
// 那么次数就是 他们共同进行腐烂， 完成后的次数。
// 还要确定是否还剩下新鲜的橘子

import "container/list"

func orangesRotting(grid [][]int) int {
	n, m := len(grid), len(grid[0])
	// 定义行为
	dir := [][2]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
	// 定义 队列
	d := list.New()
	// 每次都要将当前阶段的所有的节点都加入到队列中进行处理。 不再是初始时只有一个 root 节点在队列中
	// 1. 初始化队列
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 2 {
				d.PushBack([2]int{i, j})
			}
		}
	}
	cnt := 0
	// 2. 进行广度优先遍历
	for d.Len() > 0 {
		length := d.Len()
		for i := 0; i < length; i++ {
			pos := d.Remove(d.Front()).([2]int)
			// 四个方向
			for _, ac := range dir {
				x := ac[0] + pos[0]
				y := ac[1] + pos[1]
				// 判断越界
				if x >= 0 && y >= 0 &&
					x < n && y < m {
					// 有新鲜橘子的地方就变腐烂
					if grid[x][y] == 1 {
						grid[x][y] = 2
						// 新变成的烂橘子，加入下一轮
						d.PushBack([2]int{x, y})
					}
				}
			}
		}
		cnt += 1
	}
	// 3. 最后判断还有 新鲜橘子没
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 1 {
				return -1
			}
		}
	}
	// 4. 判断是否有腐烂的橘子，没有腐烂的橘子，那就没有橘子。返回0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 2 {
				return cnt - 1
			}
		}
	}
	return 0
}

// 更改下， 用一个 freshCnt 记录新鲜橘子的数量可以简化不好操作，比上面多几个遍历，性能也提高了。
func orangesRotting(grid [][]int) int {
	n, m := len(grid), len(grid[0])
	// 定义行为
	dir := [][2]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
	// 定义 队列
	d := list.New()
	// 每次都要将当前阶段的所有的节点都加入到队列中进行处理。 不再是初始时只有一个 root 节点在队列中
	// 1. 初始化队列
	// 并记录新鲜橘子的个数
	freshCnt := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 2 {
				d.PushBack([2]int{i, j})
			}
			if grid[i][j] == 1 {
				freshCnt += 1
			}
		}
	}
	// 判断是否没有新鲜橘子可感染
	if freshCnt == 0 {
		return 0
	}
	cnt := 0
	// 2. 进行广度优先遍历
	for d.Len() > 0 {
		length := d.Len()
		for i := 0; i < length; i++ {
			pos := d.Remove(d.Front()).([2]int)
			// 四个方向
			for _, ac := range dir {
				x := ac[0] + pos[0]
				y := ac[1] + pos[1]
				// 判断越界
				if x >= 0 && y >= 0 &&
					x < n && y < m {
					// 有新鲜橘子的地方就变腐烂
					if grid[x][y] == 1 {
						grid[x][y] = 2
						// 新鲜橘子树 减一
						freshCnt -= 1
						// 新变成的烂橘子，加入下一轮
						d.PushBack([2]int{x, y})
					}
				}
			}
		}
		cnt += 1
	}
	// 3. 最后判断还有 新鲜橘子没
	if freshCnt != 0 {
		return -1
	}
	return cnt - 1
}
